package chapter02;

import java.util.Arrays;

public class MinDistance72 {
    /**
     * 记忆化搜索
     * process(i,j) str1的前i个字符和str2的前j个字符匹配最少的操作次数
     * 下标 str1:0~i-1    str2:0~j-1
     * 递归出口
     *  1).i==0 str1的0个字符和str2的j个字符匹配 只能添加j个字符
     *     return j
     *  2).j==0 str1的i个字符和str2的0个字符匹配 只能删除i个字符
     *    return i
     *  3).其他情况
     *     a).str1的前i-1个字符和str2的前j个字符匹配 只需删除str1[i-1]
     *        process(i-1,j)+1
     *     b).str1的前i个字符和str2的前j-1个字符匹配 只需将str1末尾添加str2[j-1]
     *        process(i,j-1)+1
     *     c).str1的前i-1个字符和str2的前j-1个字符匹配 只需观察str1第i个字符和str2第j个字符
     *        如果相同 无需替换；如果不同 需要一次替换
     *        process(i-1,j-1)+str[i-1]==str2[j-1]?0:1
     * 递归过程会有重复解 添加一个缓冲数组dp[i][j] str1的前i个字符和str2的前j个字符匹配最少的操作次数
     * 递归改动态规划
     */
    public int minDistance(String word1, String word2) {
        char[] str1=word1.toCharArray();
        char[] str2=word2.toCharArray();
        int[][] dp=new int[str1.length+1][str2.length+1];
        for(int i=0;i<dp.length;i++){
            Arrays.fill(dp[i],-1);
        }
        return process(word1.length(),word2.length(),str1,str2,dp);
    }

    public int process(int len1,int len2,char[] str1,char[] str2,int[][] dp){
        if(dp[len1][len2]!=-1){
            return dp[len1][len2];
        }
        if(len1==0){
            dp[len1][len2]=len2;
            return dp[len1][len2];
        }
        if(len2==0){
            dp[len1][len2]=len1;
            return dp[len1][len2];
        }
        int res;
        if(str1[len1-1]==str2[len2-1]){
            res=process(len1-1,len2-1,str1,str2,dp);
        }else{
            res=process(len1-1,len2-1,str1,str2,dp)+1;
        }
        res=Math.min(Math.min(process(len1,len2-1,str1,str2,dp)+1,process(len1-1,len2,str1,str2,dp)+1),res);
        dp[len1][len2]=res;
        return dp[len1][len2];
    }

    //动态规划
    public int minDistance1(String word1, String word2){
        char[] str1=word1.toCharArray();
        char[] str2=word2.toCharArray();
        int[][] dp=new int[str1.length+1][str2.length+1];
        for(int i=0;i<dp.length;i++){
            dp[i][0]=i;
        }
        for(int j=0;j<dp[0].length;j++){
            dp[0][j]=j;
        }
        for(int i=1;i<dp.length;i++){
            for(int j=1;j<dp[0].length;j++){
                if(str1[i-1]==str2[j-1]){
                    dp[i][j]=dp[i-1][j-1];
                }else{
                    dp[i][j]=dp[i-1][j-1]+1;
                }
                dp[i][j]=Math.min(dp[i][j],Math.min(dp[i-1][j],dp[i][j-1])+1);
            }
        }
        return dp[dp.length-1][dp[0].length-1];
    }
}
